Müller menjaringkan 68 gol dalam 62 perlawanan untuk pasukan Jerman Barat. Beliau merupakan penjaring terbanyak pasukan Jerman sepanjang zaman sehinggalah rekod tersebut dikejutkan oleh Miroslav Klose pada 2014 walaupun Klose memerlukan kemunculan antarabangsa dua kali ganda daripada Müller. Klose menjaringkan gol ke-69nya dalam kemunculan antarabangsanya ke-132.[9] Kerjaya antarabangsa Müller bermula pada tahun 1966 dan tamat pada 7 Julai 1974 dengan menjulang kejayaan Piala Dunia 1974 di negara tanah airnya.[10] Beliau menjaringkan gol kemenangan buat pasukannya menewaskan Belanda yang dibintangi Johan Cruyff 2-1 pada perlawanan akhir. Empat gol di kejohanan tersebut dan sepuluh gol beliau di Piala Dunia 1970 meletakkan beliau penjaring terbanyak dalam saingan Piala Dunia dengan 14 gol dicetak. Rekod Müller dicabar sehinggalah edisi Piala Dunia 2006, turut diadakan di Jerman apabila rekod tersebut dipecahkan Ronaldo dari Brazil. Müller turut mengambil bahagian dalam UEFA Euro 1972 dan menjadi penjaring terbanyak kejohanan dengan empat gol selain merangkul kejuaraan Eropah bersama pasukan Jerman Barat.